package leetcode;

import java.util.Arrays;

/**
 * 322. 零钱兑换
 */
public class Solution322 {
    
//    public int coinChange(int[] coins, int amount) {
//        return coinChange1(coins,amount);
//    }
//
//    private int coinChange1(int[] coins, int amount) {
//        if(amount==0) return 0;
//        if(amount<=0) return -1;
//        int res = Integer.MAX_VALUE;
//        for (int i = 0; i < coins.length; i++) {
//            int resTemp = coinChange1(coins,amount - coins[i]);
//            if(resTemp==-1) continue;
//            res = Math.min(resTemp+1,res);
//        }
//        return res ==Integer.MAX_VALUE ?-1:res;
//    }

//    int[] note = null;
//    public int coinChange(int[] coins, int amount) {
//        note = new int[amount+1];
//        Arrays.fill(note,-666);
//        return coinChange1(coins,amount);
//    }
//
//    private int coinChange1(int[] coins, int amount) {
//        if(amount==0) return 0;
//        if(amount<=0) return -1;
//        if(note[amount]!=-666){
//            return note[amount];
//        }
//        int res = Integer.MAX_VALUE;
//        for (int i = 0; i < coins.length; i++) {
//            int resTemp = coinChange1(coins,amount - coins[i]);
//            if(resTemp==-1) continue;
//            res = Math.min(resTemp+1,res);
//            note[amount] = res;
//        }
//        return res ==Integer.MAX_VALUE ?-1:res;
//    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 数组大小为 amount + 1，初始值也为 amount + 1
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                // 子问题无解，跳过
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);

            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        Solution322 solution322 = new Solution322();
        int[] test = new int[]{ 2};
        solution322.coinChange(test,3);
    }
}
